package leetCode.firstWeek;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Code_46 {
  List<List<Integer>> res = new LinkedList<>();

  public List<List<Integer>> permute(int[] nums) {
    Arrays.sort(nums);
    List<Integer> tmp = new LinkedList<>(); // 暂存结果的List
    List<Integer> left = new LinkedList<>(); // 剩余的数字
    for (int i : nums) {
      left.add(i);
    }
    recrusion(tmp, left);
    return res;
  }

  public void recrusion(List<Integer> tmp, List<Integer> left) {
    if (left.size() == 0) {
      res.add(tmp);
      return;
    }
    for (int i = 0; i < left.size(); i++) {
      List<Integer> tmpTmp = new LinkedList<>(tmp);
      List<Integer> leftTmp = new LinkedList<>(left);
      tmpTmp.add(leftTmp.get(i));
      leftTmp.remove(i);
      recrusion(tmpTmp, leftTmp);
    }
  }
}
